The invention relates generally to a signal processing method and apparatus. The invention is particularly applicable to the field of image data processing and compression, for both data representative of two dimensional images and time sequences of such images.
Image compression techniques generally allow an image to be transmitted in coded form over a communications channel with a reduced number of data bits compared to that required to transmit an uncoded image. As a consequence of the reduction in data that is transmitted, the received image is generally degraded in quality from the original.
Transform coding is a known compression technique involving a transformation of image data to generate a sequence of coefficients. These coefficients can be encoded for transmission. Each coefficient may be encoded, for example, by a number of bits based upon the logarithm of the variance for a particular coefficient. At the receiver, the coded coefficient data may be used to reconstruct the original coefficients. Then the inverse of the original transform may be Performed to obtain an image representative of the original data.
One form of transform coding, block image coding, accommodates localized variations in image characteristics. With block image coding, a digitized function (here referred to as an "image") is decomposed into small rectangular regions (or "blocks") which are transform coded and transmitted through a communications channel (generally a digital channel). At the receiver, the blocks are decoded and re-assembled in order to reconstruct the image. In a typical situation, an image composed of an array of 256.times.256 picture elements (pixels) can be viewed as an array of 16.times.16 blocks, where each block contains 16.times.16 pixels.
The image is blocked before coding so that the data to be processed by the coder may be limited, and often permit adaptation of the coder to the particular characteristics of each block. With an efficient coding algorithm, block image coding provides significant data compression for a given picture quality.
Use of The Discrete Cosine Transform (DCT) is known to be a highly efficient way to code image data blocks, particularly when followed by an adaptive quantization scheme. The DCT is a linear transformation that generates a block of pixels, with each new pixel being a linear combination of all the input pixels of the original block. One linear transform is distinguishes from others by the set of coefficients used in the linear combinations that define each transformed pixel. The particular set used in the DCT has the property of approximating closely what would be a statistically-optimal set, and at the same time leading to a fast computation algorithm. The "almost-optimality" of the DCT implies that the degree of data compression obtained is very close to the theoretical maximum that can be achieved for any given reconstruction-error level.
The 2-dimensional (2D) DCT has been shown to be particularly useful in an image processing system for pattern recognition and noise reduction, and in a video transmission and reception system for splitting up, compressing and then transmitting video frame data followed by reconstruction of video frames in which the spatial redundancy has been removed at the transmitter by an intra-frame transform coding technique.
In addition, 2D DCT devices may be used in a high-definition television (HDTV) receiver capable of accommodating different transmission formats and different field rates, and in low-bit-rate video communication systems. Such devices can also be used in a transmitter for video transform coding to remove the spatial redundancy and for interframe motion-compensated predictive coding to remove the temporal redundancy.
However, to process a 1000-line video at 30 frame/s rate, a 2D DCT device would be required to perform more than 2 billion arithmetic operation/s. The required number of operations per second present a formidable problem for the conventional VLSI implementation. In fact, using conventional techniques, such implementation would require an extremely high level of parallel processing requiring relatively high numbers of discrete devices, large power consumption and large physical size.
Accordingly, it is an object of the present invention to provide an improved DCT-based data processing system.
Another object is to provide a high through-put, low power, low cost implementation of DCT-based data processing systems.